import java.util.Arrays;

public class Solution698 {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if (Arrays.stream(nums).sum()%k!=0){
            return false;
        }else{
            int target=Arrays.stream(nums).sum()/k;
            Arrays.sort(nums);
            if (nums[nums.length-1]>target){
                return false;
            }
            int[] f=new int[1<<nums.length];
            return dfs(0,0,0,nums,target,f,k);
        }
    }

    private boolean dfs(int nums, int now, int state, int[] arr,int target,int[] f,int k) {
        if (f[state]==0){
            if (now==k-1){
                f[state]=1;
            }else{
                for (int i=arr.length-1;i>=0;i--){
                    if (nums+arr[i]<=target  && (state&(1<<i))==0){
                        if (nums+arr[i]==target){
                            if (dfs(0,now+1,state|(1<<i),arr,target,f,k)){
                                f[state]=1;
                                break;
                            }
                        }else{
                            if (dfs(nums+arr[i],now,state|(1<<i),arr,target,f,k)){
                                f[state]=1;
                                break;
                            }
                        }
                    }
                }
            }
            if (f[state]==0){
                f[state]=-1;
            }
        }
        return f[state]==1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution698().canPartitionKSubsets(new int[]{4, 3, 2, 3, 5, 2, 1},4));
    }
}
